Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 1
SNO
Experiment
1
Design and implement C/C++ Program to find Minimum Cost Spanning Tree of a
given connected undirected graph using Kruskal's algorithm.
2
Design and implement C/C++ Program to find Minimum Cost Spanning Tree of a
given connected undirected graph using Prim's algorithm.
3
a. Design and implement C/C++ Program to solve All-Pairs Shortest Paths
problem using Floyd's algorithm.
b. Design and implement C/C++ Program to find the transitive closure using
Warshal's algorithm.
4
Design and implement C/C++ Program to find shortest paths from a given vertex
in a weighted connected graph to other vertices using Dijkstra's algorithm.
5
Design and implement C/C++ Program to obtain the Topological ordering of
vertices in a given digraph.
6
Design and implement C/C++ Program to solve 0/1 Knapsack problem using
Dynamic Programming method.
7
Design and implement C/C++ Program to solve discrete Knapsack and
continuous Knapsack problems using greedy approximation method.
8
Design and implement C/C++ Program to find a subset of a given set S = {sl ,
s2,.....,sn} of n positive integers whose sum is equal to a given positive integer d.
9
Design and implement C/C++ Program to sort a given set of n integer elements
using Selection Sort method and compute its time complexity. Run the program
for varied values of n> 5000 and record the time taken to sort. Plot a graph of the
time taken versus n. The elements can be read from a file or can be generated
using the random number generator.
10
Design and implement C/C++ Program to sort a given set of n integer elements
using Quick Sort method and compute its time complexity. Run the program for
varied values of n> 5000 and record the time taken to sort. Plot a graph of the
time taken versus n. The elements can be read from a file or can be generated
using the random number generator.
11
Design and implement C/C++ Program to sort a given set of n integer elements
using Merge Sort method and compute its time complexity. Run the program for
varied values of n> 5000, and record the time taken to sort. Plot a graph of the
time taken versus n. The elements can be read from a file or can be generated
using the random number generator.
12
Design and implement C/C++ Program for N Queen's problem using
Backtracking.
The solutions are coded in C++. Code Blocks as the integrated development environment
(IDE). GNU Plot for plotting the graph for sorting algorithms. (OS: Windows/Ubuntu)
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 2
1.Design and implement C/C++ Program to sort a given set of n integer elements using
Selection Sort method and compute its time complexity. Run the program for varied
values of n> 5000 and record the time taken to sort. Plot a graph of the time taken
versus n. The elements can be read from a file or can be generated using the random
number generator.
Algorithm:
Program:
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <ctime>
#include <chrono>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;
vector <int> numList;
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 3
// Function for Selection sort
void selectionSort( int n)
{
int i, j, min_idx,t;
for (i = 0; i < n - 1; i++) {
min_idx = i;
for (j = i + 1; j < n; j++)
{
if (numList[j] < numList[min_idx])
min_idx = j;
}
if (min_idx != i)
t = numList[i];
numList[i] = numList[min_idx];
numList[min_idx] = t;
}
}
void fnDispArray(int n)
{
int i;
for(i=0;i<n;i++)
{
cout << setw(8) << numList[i] << endl;
}
}
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 4
void fnGenRandArray(int n)
{
int i,val;
srand(time(NULL));
for(i=0;i<n;i++)
{
val = rand()%10000+5000;
numList.push_back(val);
}
}
int main()
{
int i, iVal,n;
cout << "\nEnter number of elements to sort : ";
cin >> n;
ofstream fout("SelectPlot.dat", ios::out);
fnGenRandArray(n);
cout << "UnSorted array: \n";
fnDispArray(n);
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 5
selectionSort(n);
cout << "Sorted array: \n";
fnDispArray(n);
for(i=5000;i<10000;i+=100)
{
fnGenRandArray(i);
auto start = std::chrono::high_resolution_clock::now();
selectionSort(i);
auto stop = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(stop - start);
fout << i << "\t" << setprecision(10) << duration.count() << endl;
}
cout << "\nData File generated and stored in file < SelectPlot.dat >.\n";
return 0;
}
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 6
OUTPUT:
Enter number of elements to sort : 10
UnSorted array:
6426
14542
8236
5541
7757
6585
7517
13949
5539
7246
Sorted array:
5539
5541
6426
6585
7246
7517
7757
8236
13949
14542
GNU PLOT:
set title "Time Complexity for Selection Sort"
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 7
set autoscale
set xlabel "Size of Input"
set ylabel "Sorting Time (microseconds)"
set grid
set output "SelectPlot.png"
plot "SelectPlot.dat" t 'Selection Sort' with lines
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 8
2. Design and implement C/C++ Program to sort a given set of n integer elements
using Merge Sort method and compute its time complexity. Run the program for varied
values of n> 5000, and record the time taken to sort. Plot a graph of the time taken
versus n. The elements can be read from a file or can be generated using the random
number generator.
Algorithm:
Program:
#include <iostream>
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 9
#include <fstream>
#include <iomanip>
#include <vector>
#include <ctime>
#include <chrono>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;
vector <int> numList;
void fnDispArray(int n)
{
int i;
for(i=0;i<n;i++)
{
cout << setw(8) << numList[i] << endl;
}
}
void fnGenRandArray(int n)
{
int i,val;
srand(time(NULL));
for(i=0;i<n;i++)
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 10
{
val = rand()%10000+5000;
numList.push_back(val);
}
}
void mergesort(int low,int mid,int high)
{
vector <int> b(0);
int i,j;
i=low;
j=mid+1;
int k=0;
while(i<=mid && j<=high)
{
if(numList[i]<numList[j])
b.push_back(numList[i++]);
else
b.push_back(numList[j++]);
}
while(i<=mid)
b.push_back(numList[i++]);
while(j<=high)
b.push_back(numList[j++]);
for (i=low;i<=high;i++)
{
numList[low+k] = b[k];
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 11
k++;
}
}
void SortArray(int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
SortArray(low,mid);
SortArray(mid+1,high);
mergesort(low,mid,high);
}
}
int main()
{
int i, iVal,n;
cout << "\nEnter number of elements to sort : ";
cin >> n;
ofstream fout("MergePlot.dat", ios::out);
fnGenRandArray(n);
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 12
cout << "UnSorted array: \n";
fnDispArray(n);
SortArray(0,n-1);
cout << "Sorted array: \n";
fnDispArray(n);
for(i=100;i<100000;i+=100)
{
fnGenRandArray(i);
auto start = std::chrono::high_resolution_clock::now();
SortArray(0,i-1);
auto stop = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(stop - start);
fout << i << "\t" << setprecision(10) << duration.count() << endl;
}
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 13
cout << "\nData File generated and stored in file < MergePlot.dat >.\n";
return 0;
}
Output:
Enter number of elements to sort : 10
UnSorted array:
14665
5942
13238
7549
11059
9698
5923
10848
8795
12168
Sorted array:
5923
5942
7549
8795
9698
10848
11059
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 14
12168
13238
14665
GNU Plot:
set title "Time Complexity for Merge Sort"
set autoscale
set xlabel "Size of Input"
set ylabel "Sorting Time (microseconds)"
set grid
set output "MergePlot.png"
plot "MergePlot.dat" t 'Merge Sort' with lines
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 15
3. Design and implement C/C++ Program to sort a given set of n integer elements
using Quick Sort method and compute its time complexity. Run the program for varied
values of n> 5000 and record the time taken to sort. Plot a graph of the time taken
versus n. The elements can be read from a file or can be generated using the random
number generator.
Algorithm:
Program:
#include <iostream>
#include <fstream>
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 16
#include <iomanip>
#include <vector>
#include <ctime>
#include <chrono>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;
vector <int> numList;
void fnDispArray(int n)
{
int i;
for(i=0;i<n;i++)
{
cout << setw(8) << numList[i] << endl;
}
}
void fnSwap(int &a,int &b)
{
int t;
t = a;
a = b;
b = t;
}
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 17
void fnGenRandArray(int n)
{
int i,val;
srand(time(NULL));
for(i=0;i<n;i++)
{
val = rand()%10000+5000;
numList.push_back(val);
}
}
int fnPartition(int l, int r)
{
int i,j;
int p;
p = numList[l];
i = l;
j = r+1;
do
{
do { i++; } while (numList[i] < p);
do { j--; } while (numList[j] > p);
fnSwap(numList[i], numList[j]);
}while (i<j);
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 18
fnSwap(numList[i], numList[j]);
fnSwap(numList[l], numList[j]);
return j;
}
void fnQuickSort(int l, int r)
{
int s;
if (l < r)
{
s = fnPartition(l, r);
fnQuickSort(l, s-1);
fnQuickSort(s+1, r);
}
}
int main()
{
int i, iVal,n;
cout << "\nEnter number of elements to sort : ";
cin >> n;
ofstream fout("QuickPlot.dat", ios::out);
fnGenRandArray(n);
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 19
cout << "UnSorted array: \n";
fnDispArray(n);
fnQuickSort(0,n-1);
cout << "Sorted array: \n";
fnDispArray(n);
for(i=100;i<100000;i+=100)
{
fnGenRandArray(i);
auto start = std::chrono::high_resolution_clock::now();
fnQuickSort(0,i-1);
auto stop = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(stop - start);
fout << i << "\t" << setprecision(10) << duration.count() << endl;
}
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 20
cout << "\nData File generated and stored in file < QuickSort.dat >.\n";
return 0;
}
Output:
Enter number of elements to sort : 10
UnSorted array:
5064
11672
7212
8147
9188
7538
7577
12207
14254
12318
Sorted array:
5064
7212
7538
7577
8147
9188
11672
12207
12318
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 21
14254
GNU Plot:
gnuplot> set xlabel "Size of Input"
gnuplot> set ylabel "Sorting Time (microseconds)"
gnuplot> set title "Time Complexity for Quick Sort"
gnuplot> set grid
gnuplot> set output "QuickPlot.png"
gnuplot> plot "QuickPlot.dat" t 'Quick Sort' with lines
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 22
4.Design and implement C/C++ Program to solve discrete Knapsack and continuous
Knapsack problems using greedy approximation method.
Algorithm:
Program:
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <cstdlib>
using namespace std;
typedef struct{
int profit;
int weight;
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 23
float profitRatio;
float fraction;
}Item;
int main()
{
vector <Item> itemList;
int iNum, i, iPos;
float knCap, remCap, totProfit;
Item a;
cout << "Enter the number of items : " ;
cin >> iNum;
cout << "Enter Knapsack capacity : ";
cin >> knCap;
for(i=0;i<iNum;i++)
{
cout << "Enter profit : "; cin >> a.profit;
cout << "Enter weight : "; cin >> a.weight;
a.profitRatio = (float)a.profit / a.weight;
a.fraction = 0.0f;
if (itemList.size() == 0)
{
itemList.push_back(a);
}
else
{
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 24
iPos=0;
while(a.profitRatio < itemList[iPos].profitRatio) iPos++;
itemList.insert(itemList.begin() + iPos,a);
}
}
remCap = knCap;
totProfit = 0.0;
for(i=0;i<iNum;i++)
{
a = itemList[i];
if(remCap <= 0)
break;
if(a.weight < remCap)
{
itemList[i].fraction = 1.0;
remCap -= itemList[i].weight;
totProfit += itemList[i].profit;
}
}
cout << "\nDISCRETE KNAPSACK GREEDY SOLUTION\n";
cout << "\nItem\tWeight\tProfit\tFraction\n";
for(i=0;i<iNum;i++)
{
cout <<setw(4) << i+1 << "\t" << setw(6) << itemList[i].weight << "\t" << setw(6) <<
itemList[i].profit << "\t" << setw(6) << setprecision(2) << itemList[i].fraction << endl;
}
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 25
cout << "nTotal Profit Earned : " << fixed << totProfit << endl;
remCap = knCap;
totProfit = 0.0;
for(i=0;i<iNum;i++)
{
itemList[i].fraction = 0.0;
}
for(i=0;i<iNum;i++)
{
a = itemList[i];
if(remCap <= 0)
break;
if(a.weight < remCap)
{
itemList[i].fraction = 1.0;
remCap -= itemList[i].weight;
totProfit += itemList[i].profit;
}
else
{
itemList[i].fraction = remCap / itemList[i].weight;
remCap -= itemList[i].weight * itemList[i].fraction;
totProfit += itemList[i].profit * itemList[i].fraction;
}
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 26
}
cout << "\nCONTINUOUS KNAPSACK GREEDY SOLUTION\n";
cout << "\nItem\tWeight\tProfit\tFraction\n";
for(i=0;i<iNum;i++)
{
cout << i+1 << "\t" << itemList[i].weight << "\t" << itemList[i].profit << "\t" <<
setprecision(2) << itemList[i].fraction << endl;
}
cout << "\nTotal Profit Earned : " << fixed << totProfit << endl;
return 0;
}
Output:
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 27
5. Design and implement C/C++ Program to solve 0/1 Knapsack problem using
Dynamic Programming method.
Algorithm:
Program:
#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;
const int MAX = 10;
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 28
int totalProfit;
int weight[MAX];
int profit[MAX];
int capacity;
int numOfObj;
int subset[MAX];
int table[MAX][MAX];
inline int max(int x, int y)
{
return (x>y)?x:y;
}
void fnCalcProfit()
{
int i,j;
for (j=0; j<=capacity; j++)
table[0][j] = 0;
for (i=0; i<=numOfObj; i++)
table[i][0] = 0;
for (i=1; i<=numOfObj; i++)
{
for (j=1; j<=capacity; j++)
{
if (j-weight[i] < 0)
table[i][j] = table[i-1][j];
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 29
else
table[i][j] = max(table[i-1][j], profit[i] + table[i-1][j-weight[i]]);
}
}
totalProfit = table[numOfObj][capacity];
cout << "\nProfit Matrix" << endl;
for(i=0;i<=numOfObj; i++)
{
for (j=0; j<=capacity; j++)
{
cout << setw(6) << table[i][j];
}
cout << endl;
}
cout << endl;
}
void fnFindSubSet()
{
int i,j;
i = numOfObj;
j = capacity;
while (i >= 1 && j >= 1)
{
if (table[i][j] != table[i-1][j])
{
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 30
subset[i] = 1;
j = j - weight[i];
}
i--;
}
cout << "Items selected for the Knapsack are : " ;
for(i=1;i<=numOfObj;i++)
{
if(subset[i] == 1)
cout << i << " ";
}
cout << endl;
cout << "Total Profit earned is " << totalProfit << endl;
}
int main()
{
int i;
totalProfit = 0;
for( i=1; i<=numOfObj; i++)
subset[i] = 0;
cout << "\n Enter the maximum number of objects : ";
cin >> numOfObj;
cout << "\n Enter the weights : n";
for (i=1; i<=numOfObj; i++)
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 31
{
cout << "\nWeight " << i << ": ";
cin >> weight[i];
}
cout << "\nEnter the profits : n";
for (i=1; i<=numOfObj; i++)
{
cout << "\nProfit " << i << ": ";
cin >> profit[i];
}
cout << "\nEnter the maximum capacity : ";
cin >> capacity;
fnCalcProfit();
fnFindSubSet();
return 0;
}
Output:
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 32
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 33
6. Design and implement C/C++ Program to find Minimum Cost Spanning Tree of a
given connected undirected graph using Kruskal's algorithm.
Algorithm:
Program:
#include <iostream>
using namespace std;
const int MAXNODES = 10;
const int INF = 9999;
struct edge
{
int u, v, cost;
};
int fnFindParent(int v, int parent[])
{
while (parent[v] != v)
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 34
v = parent[v];
return v;
}
void fnUnion_ij(int i, int j, int parent[])
{
if(i < j)
parent[j] = i;
else
parent[i] = j;
}
void fnInputGraph(int m, edge e[])
{
int i, j, k, cost;
for(k=0; k<m; k++)
{
cout << "Enter edge and cost in the form u, v, w : \n";
cin >> i >> j >> cost;
e[k].u = i;
e[k].v = j;
e[k].cost = cost;
}
}
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 35
int fnGetMinEdge(edge e[], int n)
{
int i, small, pos;
small = INF;
pos = -1;
for(i=0; i<n; i++)
{
if(e[i].cost < small)
{
small = e[i].cost;
pos = i;
}
}
return pos;
}
void fnKruskal(int n, edge e[], int m)
{
int i, j, count, k, sum, u, v, t[MAXNODES][2], pos;
int parent[MAXNODES];
count = 0;
k = 0;
sum = 0;
for(i=0; i<n; i++)
{
parent[i] = i;
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 36
}
while(count != n-1)
{
pos = fnGetMinEdge(e,m);
if(pos == -1)
{
break;
}
u = e[pos].u;
v = e[pos].v;
i = fnFindParent(u,parent);
j = fnFindParent(v,parent);
if(i != j)
{
t[k][0] = u;
t[k][1] = v;
k++;
count++;
sum += e[pos].cost;
fnUnion_ij(i, j, parent);
}
e[pos].cost = INF;
}
if(count == n-1)
{
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 37
cout << "\nSpanning tree exists";
cout << "\nThe Spanning tree is shown below\n";
for(i=0; i<n-1; i++)
cout << t[i][0] << " " << t[i][1] << endl;
cout << "\nCost of the spanning tree : " << sum << endl;
}
else
cout << "\nThe spanning tree does not exist" << endl;
}
int main()
{
int n = 6, m = 20;
edge e[2*MAXNODES] = {{0,1,6},{1,4,4},{4,5,6},{5,3,2},{3,0,5},{0,2,1},
{1,2,5},{3,2,2},{4,2,6},{5,2,3} };
cout << "Enter the number of nodes : ";
cin >> n;
cout << "Enter the number of edges : ";
cin >> m;
fnKruskal(n, e, m);
return 0;
}
OUTPUT:
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 38
Enter the number of nodes : 6
Enter the number of edges : 10
Enter edge and cost in the form u, v, w :
0 1 6
Enter edge and cost in the form u, v, w :
1 4 4
Enter edge and cost in the form u, v, w :
4 5 6
Enter edge and cost in the form u, v, w :
5 3 2
Enter edge and cost in the form u, v, w :
3 0 5
Enter edge and cost in the form u, v, w :
0 2 1
Enter edge and cost in the form u, v, w :
1 2 5
Enter edge and cost in the form u, v, w :
3 2 2
Enter edge and cost in the form u, v, w :
4 2 6
Enter edge and cost in the form u, v, w :
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 39
5 2 3
Spanning tree exists
The Spanning tree is shown below
0 2
5 3
3 2
1 4
1 2
Cost of the spanning tree : 14
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 40
7. Design and implement C/C++ Program to find Minimum Cost Spanning Tree of a
given connected undirected graph using Prim's algorithm.
Algorithm:
Program:
#include <iostream>
using namespace std;
const int MAXNODES = 10;
void fnPrims(int n, int cost[MAXNODES][MAXNODES])
{
int i, j, u, v, min;
int sum, k, t[MAXNODES][2], p[MAXNODES], d[MAXNODES], s[MAXNODES];
int source, count;
min = 9999;
source = 0;
for(i=0; i<n; i++)
{
for(j=0; j<n; j++)
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 41
{
if(cost[i][j] != 0 && cost[i][j] <= min)
{
min = cost[i][j];
source = i;
}
}
}
for(i=0; i<n; i++)
{
d[i] = cost[source][i];
s[i] = 0;
p[i] = source;
}
s[source] = 1;
sum = 0;
k = 0;
count = 0;
while (count != n-1)
{
min = 9999;
u = -1;
for(j=0; j<n; j++)
{
if(s[j] == 0)
{
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 42
if(d[j] <= min)
{
min = d[j];
u = j;
}
}
}
t[k][0] = u;
t[k][1] = p[u];
k++;
count++;
sum += cost[u][p[u]];
s[u] = 1;
for(v=0; v<n; v++)
{
if(s[v]==0 && cost[u][v]<d[v])
{
d[v] = cost[u][v];
p[v] = u;
}
}
}
if(sum >= 9999)
cout << "\nSpanning tree does not exist";
else
{
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 43
cout << "\nThe spanning tree exists and minimum cost spanning tree is n";
for(i=0; i<k; i++)
cout << t[i][1] << " " << t[i][0] << endl;
cout << "\nThe cost of the minimum cost spanning tree is " << sum << endl;
}
}
int main()
{
int a[MAXNODES][MAXNODES] = {
{0, 3, 9999, 7, 9}, {3, 0, 4, 2, 9999}, {9999, 4, 0, 5, 6},
{7, 2, 5, 0, 4}, {9, 9999, 6, 4, 0}};
int n = 5;
int i, j;
cout << "Enter the number of vertices : ";
cin >> n;
cout << "Enter the Cost Adjacency Matrix" << endl;
for(i=0; i<n; i++)
for(j=0; j<n; j++)
cin >> a[i][j];
fnPrims(n,a);
return 0;
}
OUTPUT:
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 44
Enter the number of vertices : 5
Enter the Cost Adjacency Matrix
0 3 9999 7 9
3 0 4 2 9999
9999 4 0 5 6
7 2 5 0 4
9 9999 6 4 0
The spanning tree exists and minimum cost spanning tree is n3 1
1 0
3 4
1 2
The cost of the minimum cost spanning tree is 13
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 45
8. Design and implement C/C++ Program to find shortest paths from a given vertex in a
weighted connected graph to other vertices using Dijkstra's algorithm.
Algorithm:
1 function Dijkstra(Graph, source):
2
3 for each vertex v in Graph.Vertices:
4 dist[v] ← INFINITY
5 prev[v] ← UNDEFINED
6 add v to Q
7 dist[source] ← 0
8
9 while Q is not empty:
10 u ← vertex in Q with minimum dist[u]
11 remove u from Q
12
13 for each neighbor v of u still in Q:
14 if dist[u] + Graph.Edges(u, v)< dist[v]:
15 dist[v] ← dist[u] + Graph.Edges(u, v)
16 prev[v] ← u
Program:
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXNODES = 10,INF = 9999;
void fnDijkstra(int c[MAXNODES][MAXNODES], int d[MAXNODES], int p[MAXNODES],
int s[MAXNODES], int so, int de, int n)
{
int i,j,a,b,min;
for (i=0;i<n;i++)
{
s[i] = 0;
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 46
d[i] = c[so][i];
p[i] = so;
}
s[so] = 1;
for (i=1;i<n;i++)
{
min = INF;
a = -1;
for (j=0;j<n;j++)
{
if (s[j] == 0)
{
if (d[j] < min)
{
min = d[j];
a = j;
}
}
}
if (a == -1) return;
s[a] = 1;
if (a == de) return;
for (b=0;b<n;b++)
{
if (s[b] == 0)
{
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 47
if (d[a] + c[a][b] < d[b])
{
d[b] = d[a] + c[a][b];
p[b] = a;
}
}
}
}
}
int main(void)
{
int
n,cost[MAXNODES][MAXNODES],dist[MAXNODES],visited[MAXNODES],path[MAXNODES]
,i,j,source,dest;
cout << "\nEnter the number of nodes: ";
cin >> n;
cout << "\nEnter the Cost Matrix: \n" << endl;
for (i=0;i<n;i++)
for (j=0;j<n;j++)
cin >> cost[i][j];
cout << "\nEnter the Source vertex" << endl;
cin >> source;
cout << "\n For Source Vertex : " << source << " shortest path to other vertices"<< endl;
for (dest=0; dest < n; dest++)
{
fnDijkstra(cost,dist,path,visited,source,dest,n);
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 48
if (dist[dest] == INF)
cout << dest << " not reachable" << endl;
else
{
cout << endl;
i = dest;
do
{
cout << i << "<--";
i = path[i];
}while (i!= source);
cout << i << " = " << dist[dest] << endl;
}
}
return 0;
}
OUTPUT:
Input Graph:
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 49
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 50
9.a. Design and implement C/C++ Program to solve All-Pairs Shortest Paths problem
using Floyd's algorithm.
Algorithm:
let dist be a |V| × |V| array of minimum distances initialized to ∞
(infinity)
for each edge (u, v) do
dist[u][v] ← w(u, v) // The weight of the edge (u, v)
for each vertex v do
dist[v][v] ← 0
for k from 1 to |V|
for i from 1 to |V|
for j from 1 to |V|
if dist[i][j] > dist[i][k] + dist[k][j]
dist[i][j] ← dist[i][k] + dist[k][j]
end if
Program:
#include <iostream>
using namespace std;
int main(void)
{
int n, i, j, k;
int floyd[10][10], cost[10][10];
cout << "\nEnter the number of vertices\n";
cin >> n;
cout << "\nEnter the Cost adjacency Matrix\n";
for(i=0;i<n;i++)
for(j=0;j<n;j++)
cin >> cost[i][j];
for(i=0;i<n;i++)
{
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 51
for(j=0;j<n;j++)
{
floyd[i][j] = cost[i][j];
}
}
for(k=0;k<n;k++)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(floyd[i][j] > (floyd[i][k] + floyd[k][j]))
floyd[i][j] = (floyd[i][k] + floyd[k][j]);
}
}
}
cout << "\nAll Pair Shortest Path Matrix\n";
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
cout << floyd[i][j] << "\t";
}
cout << endl;
}
cout << "\n";
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 52
return 0;
}
Output:
Graph:
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 53
9.b. Design and implement C/C++ Program to find the transitive closure using
Warshall's algorithm.
Algorithm:
Program:
#include <iostream>
using namespace std;
const int MAX = 100;
void WarshallTransitiveClosure(int graph[MAX][MAX], int numVert)
{
int i,j,k;
for (k=0; k<numVert; k++)
{
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 54
for (i=0; i<numVert; i++)
{
for (j=0; j<numVert; j++)
{
if (graph[i][j] || (graph[i][k] && graph[k][j]))
graph[i][j] = 1;
}
}
}
}
int main(void)
{
int i, j, numVert;
int graph[MAX][MAX];
cout << "Warshall's Transitive Closure" << endl;
cout << "Enter the number of vertices : " ;
cin>>numVert;
cout << "Enter the adjacency matrix :-" << endl;
for (i=0; i<numVert; i++)
for (j=0; j<numVert; j++)
cin>>graph[i][j];
WarshallTransitiveClosure(graph, numVert);
cout << "\nThe transitive closure for the given graph is :-" << endl;
for (i=0; i<numVert; i++)
{
for (j=0; j<numVert; j++)
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 55
{
cout << graph[i][j] << "\t";
}
cout << "" << endl;
}
return 0;
}
Output:
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 56
10. Design and implement C/C++ Program to obtain the Topological ordering of
vertices in a given digraph.
Algorithm:
L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edge
while S is not empty do
remove a node n from S
add n to L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S
if graph has edges then
return error (graph has at least one cycle)
else
return L (a topologically sorted order)
Program:
#include <iostream>
using namespace std;
const int MAX = 10;
void fnTopological(int graph[MAX][MAX], int n)
{
int in[MAX], out[MAX], stack[MAX], top=-1;
int i,j,k=0;
for (i=0;i<n;i++)
{
in[i] = 0;
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 57
for (j=0; j<n; j++)
if (graph[j][i] == 1)
in[i]++;
}
while(1)
{
for (i=0;i<n;i++)
{
if (in[i] == 0)
{
stack[++top] = i;
in[i] = -1;
}
}
if (top == -1)
break;
out[k] = stack[top--];
for(i=0;i<n;i++)
{
if (graph[out[k]][i] == 1)
in[i]--;
}
k++;
}
cout<<"Topological Sorting (JOB SEQUENCE) is:- \n";
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 58
for (i=0;i<k;i++)
cout<<"\t"<< out[i] + 1;
cout<<"\n";
}
int main( int argc, char **argv)
{
int graph[MAX][MAX],n;
int i,j;
cout<<"Topological Sorting Algorithm\n";
cout<<"\nEnter the number of vertices : ";
cin>>n;
cout<<"Enter the adjacency matrix (graph should be a DAG)\n";
for (i=0; i<n; i++)
for (j=0; j<n; j++)
cin>>graph[i][j];
fnTopological(graph,n);
cout<<"\n";
return 0;
}
OUTPUT:
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 59
11. Design and implement C/C++ Program to find a subset of a given set S = {s1,
s2,.....,sn} of n positive integers whose sum is equal to a given positive integer d.
Algorithm:
Program:
#include <iostream>
using namespace std;
int subset(int n,int d,int values[])
{
int sum,k,i,included[10];
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 60
static int foundSoln = 0;
static int count = 0;
for(i=1;i<=n;i++)
included[i] = 0;
sum = 0;
k = 1;
included[k] = 1;
while(1)
{
if(k <= n && included[k] == 1)
{
if(sum + values[k] == d)
{
foundSoln = 1;
++count;
cout<<"SOLUTION "<<count<<" IS {";
for(i=1;i<=n;i++)
{
if(included[i] == 1)
cout<<values[i]<<" ";
}
cout<<" }\n";
included[k] = 0;
}
else if(sum + values[k] < d)
sum += values[k];
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 61
else
included[k] = 0;
}
else
{
k--;
while(k>0 && included[k] == 0)
{
k--;
}
if(k == 0)
break;
included[k] = 0;
sum = sum - values[k];
}
k = k+1;
included[k] = 1;
}
return foundSoln;
}
int main()
{
int n,d,i,values[10];
cout<<"Enter the number of elements : ";
cin>>n;
cout<<"Enter the values of the elements (in ascending order) : \n";
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 62
for(i=1;i<=n;i++)
cin>>values[i];
cout<<"\nEnter the sum value : ";
cin>>d;
cout<<"\n";
if (!subset(n,d,values))
cout<<"nThe problem instance doesnt have any solution\n";
else
cout<<"\nThe sets are the required solution to the given instance.\n";
return 0;
}
Output:
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 63
12. Design and implement C/C++ Program for N Queen's problem using Backtracking.
Algorithm:
Program:
#include <iostream>
#include <cstdlib>
using namespace std;
const int MAX = 10;
int SolnCount =0;
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 64
bool fnCheckPlace(int KthQueen, int ColNum, int colVec[MAX])
{
for(int i=0; i<KthQueen; i++)
{
if(colVec[i] == ColNum || abs(colVec[i]-ColNum) == abs(i-KthQueen))
return false;
}
return true;
}
void fnChessBoardShow(int n, int colVec[MAX])
{
cout << "\nSolution #" << SolnCount+1 << endl << endl;
for (int i=0; i<n; i++)
{
for (int j=0; j<n; j++)
{
if (j == colVec[i])
cout << "Q ";
else
cout << "# ";
}
cout << endl;
}
cout << endl;
}
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 65
int NQueen(int k,int n, int colVec[MAX])
{
static int flag;
for(int i=0; i<n; i++)
{
if(fnCheckPlace(k,i,colVec) == true)
{
colVec[k] = i;
if(k == n-1)
{
fnChessBoardShow(n,colVec);
SolnCount++;
flag = 1;
return flag;
}
NQueen(k+1, n, colVec);
}
}
return flag;
}
int main(void)
{
int n;
int colVec[MAX];
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 66
cout << "Enter the number of queens : ";
cin >> n;
if (!NQueen(0,n,colVec))
cout << "No solution exists for the given problem instance." << endl;
else
cout << "Number of solution for the given problem instance is : "
<< SolnCount << endl;
return 0;
}
Output:
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 67
VIVA VOICE QUESTIONS
1.What is the importance of analyzing algorithms?
Answer: Analyzing algorithms helps us understand their efficiency in terms of time and
space. It allows us to compare different approaches to solving the same problem and
helps in predicting how an algorithm will perform as the input size grows.
2.What is meant by time complexity?
Answer: Time complexity measures the amount of time an algorithm takes to run as a
function of the size of its input. It gives an idea of how efficiently an algorithm solves a
problem.
3.How is time complexity typically expressed?
Answer: Time complexity is expressed using Big O notation, which provides an upper
bound on the asymptotic runtime of an algorithm in terms of the input size.
4.What is the significance of Big O notation in algorithm analysis?
Answer: Big O notation helps us classify algorithms according to how their runtime or
space requirements grow with input size. It provides a standardized way to compare the
efficiency of algorithms.
5.Explain the difference between worst-case, best-case, and average-case time
complexity.
• Answer:
o Worst-case time complexity: This describes the maximum time an
algorithm takes for any input size.
o Best-case time complexity: This is the minimum time an algorithm takes
for any input size.
o Average-case time complexity: This is the expected time an algorithm
takes averaged over all possible inputs.
6.How do you calculate the time complexity of an algorithm?
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 68
Answer: Time complexity is often determined by analyzing the number of operations an
algorithm performs in relation to its input size. For example, counting iterations in loops
or recursive calls.
7.Why is space complexity important?
Answer: Space complexity measures the amount of memory an algorithm uses in
relation to its input size. It's crucial for determining how much memory an algorithm will
require, especially when dealing with large datasets or limited memory environments.
8.How can algorithm analysis help in practical applications?
• Answer: Algorithm analysis helps in choosing the most efficient algorithm for
solving a problem, optimizing performance in software applications, and
predicting how systems will perform under different conditions or input sizes
9.What is the Divide and Conquer strategy in algorithm design?
Answer: Divide and Conquer is a problem-solving paradigm where a problem is divided
into smaller subproblems that are solved recursively. The solutions to the subproblems
are then combined to solve the original problem.
10.What are the three main steps involved in the Divide and Conquer approach?
Answer: The main steps are:
Divide: Break the problem into smaller, manageable subproblems.
Conquer: Solve the subproblems recursively. If the subproblems are small
enough, solve them directly.
Combine: Combine the solutions of the subproblems to solve the original
problem.
10.Can you give an example of a problem that can be solved using Divide and
Conquer?
Answer: Merge Sort is a classic example where the array is divided into two halves,
sorted recursively, and then merged back together. Finding the maximum or minimum
value in an array using a Divide and Conquer approach is another example.
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 69
11.What is the time complexity of algorithms designed using Divide and Conquer?
Answer: The time complexity varies depending on the problem, but many Divide and
Conquer algorithms have a time complexity of O(n log n), where n is the size of the
input. This is due to the recursive division and combination steps.
12.How does Divide and Conquer differ from dynamic programming?
Answer: Divide and Conquer breaks a problem into independent subproblems and
solves each subproblem recursively. Dynamic programming, on the other hand, solves
problems by combining solutions to subproblems and storing the results to avoid
redundant computations.
13.What are the advantages of using Divide and Conquer algorithms?
Answer: Divide and Conquer algorithms are often efficient and can be parallelized easily
since they involve independent subproblems. They also help in designing clear, modular
solutions to complex problems.
14.When would you not use Divide and Conquer?
Answer: Divide and Conquer may not be suitable for problems where the division step
results in a large number of subproblems with overlapping solutions. It's also less
effective for problems where the combination step is computationally expensive.
15.How do you determine the base case in a Divide and Conquer algorithm?
Answer: The base case is determined by identifying the smallest subproblem that can
be solved directly without further division. For example, in Merge Sort, the base case is
when the array size is 1.
16.What are some classic algorithms that employ the Divide and Conquer
strategy?
Answer: Merge Sort, Quick Sort, Binary Search, and Strassen's algorithm for matrix
multiplication are also based on the Divide and Conquer approach.
17.Can you explain how Merge Sort works using the Divide and Conquer strategy?
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 70
Answer: Merge Sort divides the array into two halves, recursively sorts each half, and
then merges the sorted halves back together. This process continues until the entire
array is sorted. It's efficient with a time complexity of O(n log n).
18.What is the Greedy method in algorithm design?
Answer: The Greedy method is a problem-solving strategy where the algorithm makes
locally optimal choices at each step with the hope of finding a global optimum solution.
It makes decisions based on the current best option without reconsidering previous
choices.
19.Can you give an example of a problem that can be solved using the Greedy
method?
Answer: The "Fractional Knapsack Problem" is a classic example where items of
certain weights and values are to be put into a knapsack to maximize the total value.
The Greedy approach here would involve selecting items based on their value-to-weight
ratio, starting with the highest ratio first.
20.What are the main components of a Greedy algorithm?
Answer: The main components include:
o Greedy Choice: Make a decision that seems best at the current moment.
o Optimal Substructure: Ensure that making a locally optimal choice leads
to a globally optimal solution.
o Iterative Selection: Continue making greedy choices until the problem is
solved.
21.What are the advantages of using the Greedy method?
Answer: Greedy algorithms are often straightforward to implement and
computationally efficient. They can provide near-optimal solutions for many problems
and are generally easy to understand and debug.
22.What is Prim's algorithm?
Answer: Prim's algorithm starts with an arbitrary vertex and grows the MST by adding
the cheapest edge that connects a vertex in the MST to a vertex outside the MST until all
vertices are included.
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 71
23.What is the time complexity of Prim's algorithm ?
Answer: Using a priority queue (min-heap), Prim's algorithm has a time complexity of
O(E log V), where E is the number of edges and V is the number of vertices in the graph.
24.What is Kruskal's algorithm ?
Answer: Kruskal's algorithm works by initially placing each vertex in its own disjoint set.
It then iterates over the sorted edges, adding an edge to the MST if it connects two
different sets (to avoid cycles) until all vertices are connected.
25. What is the time complexity of Kruskal's algorithm using a union-find data
structure?
Answer: Using the union-find data structure (with path compression and union by rank),
Kruskal's algorithm has a time complexity of O(E log V), where E is the number of edges
and V is the number of vertices in the graph.
26.How does Dijkstra's algorithm work?
Answer: Dijkstra's algorithm initializes a distance to the source vertex as 0 and all other
distances as infinity. It iteratively selects the vertex with the smallest known distance,
updates the distances to its neighbors, and marks it as visited until all vertices are
processed.
27.What is the time complexity of Dijkstra's algorithm using a priority queue?
Answer: Using a priority queue (min-heap), Dijkstra's algorithm has a time complexity of
O((V + E) log V), where V is the number of vertices and E is the number of edges in the
graph.
28.How does the Floyd-Warshall algorithm work?
Answer: The Floyd-Warshall algorithm initializes a distance matrix where each entry (i, j)
represents the shortest distance from vertex i to vertex j. It then iteratively updates the
matrix by considering all vertices as intermediate points until all pairs of vertices have
been considered.
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 72
29.What is the time complexity of the Floyd-Warshall algorithm?
Answer: The Floyd-Warshall algorithm has a time complexity of O(V^3), where V is the
number of vertices in the graph. This makes it suitable for dense graphs with relatively
small numbers of vertices.
30: What is the N-Queens problem?
The N-Queens problem involves placing N queens on an N x N chessboard such that no
two queens threaten each other. This means no two queens can share the same row,
column, or diagonal.
The N-Queens problem is typically solved using a backtracking algorithm.
31 Why can't the N-Queens problem be solved using a greedy algorithm?
A greedy algorithm can't be used because it makes decisions based only on local
optimization (current row/column), and it does not ensure a globally optimal solution
where all queens are non-threatening.
32: How does the backtracking algorithm work for the N-Queens problem?
The backtracking algorithm places queens one by one in different rows, starting from
the leftmost column. It checks for safety (non-threatening position) before placing a
queen. If placing a queen leads to a solution, it is kept; otherwise, it is removed
(backtracked), and the algorithm tries the next position.
33. What is the Subset Sum problem?
The Subset Sum problem involves determining whether there is a subset of a given set
of integers that sums up to a given target sum.
35. What is topological sorting?
Topological sorting is an ordering of vertices in a directed acyclic graph (DAG) such that
for every directed edge
uvuv
uv from vertex
uu
u to vertex
vv
v,
uu
u appears before
vv
v in
the ordering.
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 73
36.Can topological sorting be applied to any graph? A2: No, topological sorting can
only be applied to directed acyclic graphs (DAGs).
37. How does the DFS-based approach work for topological sorting?
The DFS-based approach involves performing a depth-first search on the graph. When
visiting a vertex, recursively visit all its adjacent vertices. After visiting all adjacent
vertices, push the vertex onto a stack. After all vertices are processed, the stack contains
the vertices in topologically sorted order.
Analysis & Design of Algorithms Lab
Department of CSE-Data Science
ACS College Of Engineering
Page 74
